/**
 * @projectName algorithm
 * @package PACKAGE_NAME
 * @className PACKAGE_NAME.FastSort
 */

import util.GeneratorRandomArr;

/**
 * FastSort
 * @description 快速排序
 * 原理：随机选择一个数作为中间数，左边是小于该数的，中间范围是等于本身的，右边是大于该数的
 * 时间复杂度：O(N*logN)
 * @author answer_wx
 * @date 2022/6/28 18:03
 * @version 1.0
 */
public class FastSort {
    // 排序范围，数组角标s-e的范围，默认e>=s
    public static void process(int[] arr, int s, int e) {
        // 如果s==e则数组只有一个值
        if (s == e) {
            return;
        }
        if (s < e) {
            int index = partition(arr, s, e);
            process(arr, s, index - 1);
            process(arr, index + 1, e);
        }

    }

    public static int partition(int[] arr, int s, int e) {
        // 指定基点数
        int p = arr[e];
        // 起始位置
        int i = s;
        for (int j = s; j < e; j++) {
            if (arr[j] < p) {
                swap(arr, j, i++);
            }
        }
        swap(arr, e, i);
        return i;
    }

    public static void swap(int[] arr, int s, int e) {
 /*       arr[s] = arr[s] ^ arr[e];
        arr[e] = arr[s] ^ arr[e];
        arr[s] = arr[s] ^ arr[e];*/
        int tmp = arr[s];
        arr[s] = arr[e];
        arr[e] = tmp;
    }

    public static void main(String[] args) {
        int[] generator = GeneratorRandomArr.generator(10, 10);
//        int[] generator = {7, 6, 5, 4, 3};
        for (int i = 0; i < generator.length; i++) {
            System.out.print(generator[i] + ",");
        }
        System.out.println();
        process(generator, 0, generator.length - 1);
        for (int i = 0; i < generator.length; i++) {
            System.out.print(generator[i] + ",");
        }
    }
}